package binaryTree;

// 模拟实现二叉树基本功能
// 树是递归实现的：所以在以下功能实现过程中基本都是使用递归去实现

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    // 首先创建一个结点类且创建构造方法
    static class TreeNode {
        char val;
        TreeNode leftNode; // 左子树
        TreeNode rightNode; //右子树（根结点）

        // 构造方法
        public TreeNode(char val) {
            this.val = val;
        }
    }

    // 根结点声明
    public TreeNode root;

    // 穷举法创建一棵树！！
    public void createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        this.root = A;
        A.leftNode = B;
        A.rightNode = C;
        B.leftNode = D;
        B.rightNode = E;
        C.leftNode = F;
        C.rightNode = G;
        E.rightNode = H;
    }


    // 递归实现遍历！！

    // 前序遍历
    void preOrder(TreeNode root) {
        // 使用递归实现，且顺序为：根--左--右
        if(root == null) {
            return ;
        }
        // 到这里说明不空
        System.out.print(root.val + " ");
        preOrder(root.leftNode);
        preOrder(root.rightNode);
    }

    /*// 注意前序遍历返回的是List类型：OJ--
    // 如果定义List放在方法里面，这里会有一个addAll方法来接收左右子树的所有结点
    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return null;
        }
        // 注意这里的参数！！！
        list.add(root.val);
        // 注意这里！！！:返回值类型
        List<Integer> leftTree = preorderTraversal1(root.leftNode);
        list.addAll(leftTree);
        List<Integer> rightTree  = preorderTraversal1(root.rightNode);
        list.addAll(rightTree);
        return list;
    }

    // 定义放在外面就不用重新接收
    List<Integer> list = new LinkedList<>();
    public List<Integer> preorderTraversal2(TreeNode root) {
        if(root == null) {
            return null;
        }
        // 注意这里的参数！！！
        list.add(root.val);
        // 注意这里！！！:返回值类型
        preorderTraversal1(root.leftNode);
        preorderTraversal1(root.rightNode);
        return list;
    }*/


    // 中序遍历
    void inOrder(TreeNode root) {
        // 同样递归+ 左--根--右
        if(root == null) {
            return ;
        }
        // 到这里说明不空
        preOrder(root.leftNode);
        System.out.print(root.val + " ");
        preOrder(root.rightNode);
    }


    // 后序遍历
    void postOrder(TreeNode root) {
        // 同样递归+ 左--右--根
        if(root == null) {
            return ;
        }
        // 到这里说明不空
        preOrder(root.leftNode);
        preOrder(root.rightNode);
        System.out.print(root.val + " ");
    }


    // 获取树中结点的个数：左树+右树+根结点1（还是需要递归）：注意返回形式的理解！！
    int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return (size(root.leftNode) + size(root.rightNode) + 1);
    }

    // or 遍历结点就++ ：==定义static全局变量
    public static int countNode;
    void sizeNode(TreeNode root) {
        // 进行结点遍历
        if(root == null) {
            return ;
        }
        //注意以下是错误的！！！
        /*// 同样需要递归
        else {
            sizeNode(root.leftNode);
            countNode++;
            sizeNode(root.rightNode);
            countNode++;
        }*/

        // 修改：
        // 如果不等于null：数量++  且进行递归（左右子树都要）+每次只要不是null就会加加
        countNode++;
        sizeNode(root.leftNode);
        sizeNode(root.rightNode);
        //为什么不要返回值，因为static全局变量只有一份，会随之改变
    }

    // 获取叶子结点个数
    // 子问题思路：左子树+右子树叶结点
    int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 注意如何获得左右子树结点！！！
        // 然后进行是否为叶子结点的判断：是就计一个
        if(root.leftNode==null && root.rightNode==null) {
            return 1;
        }
        // 再必须递归：左右子树
        return getLeafNodeCount(root.leftNode) + getLeafNodeCount(root.rightNode);
    }

    // 遍历思路：左右子树均为空时 ==定义static全局变量
    public static int leafCount;
    void getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return ;
        }
        if(root.leftNode==null && root.rightNode==null) {
            leafCount++;
        }
        // 注意遍历方法！！
        // 同样直接递归进行左右子树遍历
        getLeafNodeCount2(root.leftNode);
        getLeafNodeCount2(root.rightNode);
    }


    // 获取第k层结点的个数：TreeNode root，int k
    // 思路：相对于根结点的第k层，k==1时的结点数（每层均有左右两个子树）
    int getKLevelNodeCount(TreeNode root, int k) {
        // 怎么递归获取结点个数
        // 修改如下：
        if(root == null) {
            return 0;
        }
        // 在每次经历左右子树的结点：左右节点分别都计1
        if(k==1) {
            return 1;
        }
        return getKLevelNodeCount(root.leftNode,k-1) +
                getKLevelNodeCount(root.rightNode,k-1);
    }


    //获取二叉树的高度：即最大深度
    // 那就是左右子树为空就是返回0，再加上本身层的1； 但是要注意：取的是左右子树的最大深度！
    // 时间复杂度： O（N）
    int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = getHeight(root.leftNode);
        int right = getHeight(root.rightNode);
        return (left<right)?(right+1):(left+1);

        // 如果省略接收左右子树高度而是直接三目运算符return，会因为重复计算二降低效率
    }


    // 检测值为value的结点是否存在
    // 遍历结点：根结点--左子树--右子树
    // 用返回值接收并进行判断
    TreeNode find(TreeNode root, char val) {
        if(root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }

        // 一定要注意！！！
        // 怎么进行返回值接收加判断！！！
        // 要记录下每次递归结果，否则在最后递归返回时会出问题
        TreeNode left = find(root.leftNode,val);
        if(left != null) {
            return left;
        }
        TreeNode right = find(root.rightNode,val);
        if(right != null) {
            return right;
        }
        // 如果不是以上结果，就是==null
        return null;
    }


    //层序遍历:
    // 层序：
    //非递归：使用队列（先进先出）--存入offer队列，且不为空isEmpty就弹出且打印，同时存入左右节点值--
    //这是一个循环操作
    //注意：队列Queen<> .. = new LinkedList<>();
    //用法：求一棵树的左视图/右视图？--阿里巴巴考——每一层的第一个结点其实就是左视图
    //求最大宽度：最大问题就是如何确定一层的节点
    void levelOrder(TreeNode root) {
        // 错误代码：
        /*Queue<Character> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root.val);
            levelOrder(root.leftNode);
            levelOrder(root.rightNode);
        } else {
            return;
        }
        while(! queue.isEmpty()) {
            System.out.print(queue.poll() +" ");
        }*/

        // 修正：
        if(root==null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 循环：如果队列不空，则：弹出一个节点，再放入该结点的左右子树结点（不空才放进去）
        while (! queue.isEmpty()) {
            TreeNode top = queue.poll();
            System.out.print(top.val + " ");
            // 注意左右节点是针对弹出的结点！
            if(top.leftNode!=null) {
                queue.offer(top.leftNode);
            }
            if(top.rightNode!=null) {
                queue.offer(top.rightNode);
            }
        }
        System.out.println();
    }


    // 层序遍历：思路2——还是依靠队列：每一层看做一个队列，总的所有又组成一个队列
    public List<List<Character>> levelOrder2(TreeNode root) {
        // key：怎么做到区分好每一层！
        List<List<Character>> list = new ArrayList<>(); // 注意声明语句
        if(root==null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (! queue.isEmpty()) {
            // queen表示一层
            int size = queue.size();
            // 创建行
            List<Character> row = new LinkedList<>();
            while(size>0) {
                // 拿出每行的元素
                TreeNode cur = queue.poll();
                size--;
                row.add(cur.val);

                // 弹出后要进行弹入
                if (cur.leftNode != null) {
                    queue.offer(cur.leftNode);
                }
                if(cur.rightNode != null) {
                    queue.offer(cur.rightNode);
                }
            }
            // 循环结束则表示当行结束
            list.add(row);
        }
        return list;
    }


    // 判断一棵树是不是完全二叉树:
    // 判断完全二叉树：依赖队列
    //就是说即使是空也要弹入队列，直到最后队列中剩余全部为null
    //（注意：当队列中存的全是null时，isEmpty也是false！）
    //当队列中循环弹出元素为null时就停止，开始查看队列中的元素是否全为null
    //循环实现
    boolean isCompleteTree(TreeNode root) {
        // 首先进行判空：空树其实也是完全二叉树
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 如何获取所有的节点放入队列！！！
        // 边弹出边弹入（即使是null也不为空队列
        while (!queue.isEmpty()) {
            // 弹出
            TreeNode cur = queue.poll();
            if (cur != null) {
                // 继续弹入
                queue.offer(cur.leftNode);
                queue.offer(cur.rightNode);
            } else {
                // 为空就停止循环,要开始判断了！！
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                return false;
            }
        }
        // 来到这：遍历完+全为null
        return true;
    }

        // 错误！！
         /*if(queue.poll() == null) {
             // 弹出为null，开始查看队列
             while(queue.poll()!=null) {
                 return false;
             }
         }
         return true;
    }*/

}
